package com.job.kujiale;

/**
 * 给一个01矩阵，1代表是陆地，0代表海洋， 如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。
 * 岛屿: 相邻陆地可以组成一个岛屿（相邻:上下左右） 判断岛屿个数。
 * 例如：输入
 * [
 * [1,1,0,0,0],
 * [0,1,0,1,1],
 * [0,0,0,1,1],
 * [0,0,0,0,0],
 * [0,0,1,1,1]
 * ]
 * 对应的输出为3
 * <p>
 * 实现一个计算岛屿数量的函数。
 */
public class B1 {
    public static void main(String[] args) {
        int[][] land = new int[][]{
                {1, 1, 0, 0, 0},
                {0, 1, 0, 1, 1},
                {0, 0, 0, 1, 1},
                {0, 0, 0, 0, 0},
                {0, 0, 1, 1, 1}
        };

        System.out.println(countLand(land));
    }

    public static int[][] lands;
    public static int[] dx = new int[]{1, 0, -1, 0};
    public static int[] dy = new int[]{0, 1, 0, -1};

    public static int countLand(int[][] land) {
        lands = land;
        int n = land.length, m = land[0].length;
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (land[i][j] == 1) {
                    count += go(i, j);
                }
            }
        }
        return count;
    }

    public static int go(int x, int y) {
        if (x < 0 || x >= lands.length) return 0;
        if (y < 0 || y >= lands[0].length) return 0;
        if (lands[x][y] == 0 || lands[x][y] == 2) return 0;
        lands[x][y] = 2;
        for (int i = 0; i < 4; i++) {
            go(x + dx[i], y + dy[i]);
        }
        return 1;
    }
}
